package nachos.threads;

import java.util.Random;

import nachos.machine.Lib;


public class LotteryScheduler extends PriorityScheduler{

	@Override
	public ThreadQueue newThreadQueue(boolean transferPriority) {//**		
		return new PriorityQueue(transferPriority);
	}
	
	@Override 
	protected ThreadState getThreadState(KThread thread){
		if (thread.schedulingState == null)
		    thread.schedulingState = new ThreadState(thread);	
		return (ThreadState) thread.schedulingState;
	}
	
	private class PriorityQueue extends PriorityScheduler.PriorityQueue{//**
		PriorityQueue(boolean transferPriority) {
			super(transferPriority);
		}
		
		@Override
		protected ThreadState pickNextThread(){			
			if (waitingQueue.isEmpty())
				return null;
			
			//calculate the sum of the lotteries
			int sum = 0;  
			if (transferPriority){
				for (KThread k : waitingQueue){
					sum += getThreadState(k).getEffectivePriority();
				}
			}else{
				for (KThread k : waitingQueue){
					sum += getThreadState(k).getPriority();
				}
			}
			
			//lottery
			int win = runLottery(sum*10);
			Lib.debug('t', "LotteryScheduler:sum of lotteries = " + sum*10 + "    winner = " + win);
			
			//return the winner thread
			ThreadState r = getThreadState(waitingQueue.getFirst());
			int p = 0;
			
			for (KThread k : waitingQueue){
				Lib.debug('t', "LotteryScheduler:waitingThread " + k.getName() + ":  p = " + getThreadState(k).priority + "  ep = " + getThreadState(k).effectivePriority);
			}
			
			for (KThread k : waitingQueue){			
				
				if (!transferPriority)
					p += 10 * getThreadState(k).getPriority();
				else 
					p += 10 * getThreadState(k).getEffectivePriority();
				if (p >= win){
					r = getThreadState(k);
					break;
				}
			}
			r.effectivePriority = r.priority;
			Lib.debug('t', "LotteryScheduler:pick out " + r.thread.getName());
			return r;
		}
		
		private int runLottery(int sum){
			Random r = new Random();
			int win = r.nextInt() % sum;
			while(win < 0)
				win = r.nextInt() % sum;
			return win;
		}
		
	}
	
	private class ThreadState extends PriorityScheduler.ThreadState{//**
		public ThreadState(KThread thread) {
			super(thread);
		}
		
		@Override
		public void waitForAccess(PriorityScheduler.PriorityQueue waitQueue) {//**
						
			//add itself into the waiting list.
			waitQueue.waitingQueue.add(thread);

			//if exists, refresh the lockholder's "lotteries"
			if (waitQueue.lockHolder != null)
				getThreadState(waitQueue.lockHolder).effectivePriority += priority;
		}
	}
	
	
}